算法概论实验七 树型动态规划方法

发表于 | 分类于 
1
2
3
4
5
6
7
8
实验七
实验目的与要求：
（1）掌握树型动态规划方法的基本思想与设计策略。


1．树中的最大独立集问题
【问题描述】
给定一个无回路的无向图（即树），设计一个动态规划算法，求出该图的最大独立集，并输出该集合中的各个顶点值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>  
#include <vector>  
#include <algorithm>  
using namespace std;  
  
const int MAXN=100;  
vector<int> G[MAXN]; //G[i]表示顶点i的邻接点 
int l[MAXN]; //结点层次  
int p[MAXN]; //根树  
int dp[MAXN]; //dp数组  
int sumC[MAXN]; //孩子DP和  
int sumS[MAXN]; //孙子DP和  
int maxL; //最大层次  
int n;  
  

  
void readTree()  
{  
    int u,v;  
    cin>>n;  
    for(int i=0;i<n-1;++i)  
    {  
        cin>>u>>v;  
        G[u].push_back(v);  
        G[v].push_back(u);  
    }  
}  
  
void dfs(int u,int fa)  
{  
    int d=G[u].size();  
     l[u]= (fa==-1)? 0: (l[fa]+1);  
     if(l[u]>maxL)  
     {  
         maxL=l[u];  
     }  
    for(int i=0;i<d;++i)  
    {  
        int v=G[u][i];  
        if(v!=fa)  
        {  
            dfs(v,p[v]=u);  
        }  
    }  
}  
  
int rootDp(int u)  
{  
    //构造u根树  
    p[u]=-1;  
    maxL=-1;  
    dfs(u,p[u]);  
    for(int i=maxL;i>=0;--i)  
    {  
        for(int j=0;j<n;++j)  
        {  
            if(l[j]==i)  
            {    
				if (sumS[j]+1>sumC[j])
				{
					dp[j]=sumS[j]+1;
				}
				else 
					dp[j] = sumC[j];
                if(i-1>=0)  
                {  
                    sumC[p[j]]+=dp[j];  
                }  
                if(i-2>=0)  
                {  
                    sumS[p[p[j]]]+=dp[j];  
                }  
            }  
        }  
    }  
    return dp[u];  
}  
  
int main()  
{  
    readTree();  
    int res=-1;  
    //分别以每个顶点为根  
    for(int i=0;i<n;++i)  
    {  
        memset(sumS,0,sizeof(sumS));  
        memset(sumC,0,sizeof(sumC));  
        int tmp;  
        if((tmp=rootDp(i))>res)  
            res=tmp;  
    }  
    cout<<res<<endl;  
    return 0;  
}